ABC161 D - Lunlun Number

提出

code:python

k = int(input())

# 事前に10^5まで調べられたらO(1)

runrun = []

def is_runurn(n):

if (len(str(n)) == 1):

return True

elif (len(str(n)) == 2):

return True

else:

return False

for i in range(1, pow(10, 5)):

if (is_runurn(i)):

runrun.append(i)

解答

code: python

import heapq

k = int(input())

# k=

# 1 -> 10, 11, 12

# 8 -> 87, 88, 89

# 9 -> 98, 99

# 次の桁の生成ルール

# ex.

# 0 -> 00, 01

# 1 -> 10, 11, 12

# 9 -> 98, 99

def next_num(n):

if n == 0:

elif n == 9:

else:

# とりあえず 1 桁の Lunlun Number を初期値にとる

heapq.heapify(queue)

for _ in range(k-1):

# 最小値を取り出す

now = heapq.heappop(queue)

# 取り出した値を使って次の桁の値を生成し queue に投げる

for next_i in next_num(now % 10):

heapq.heappush(queue, now * 10 + next_i)

# k 回目に取り出す最小値

メモ

提出

code: python

k = int(input())

# 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23, 32, 33, 34...

# 末尾に -=1, 0, +=1 を足していく

# ある程度求めればsortしたら答えが出る

def dfs(n, dp):

if n > k or int(str(n) + last) >= pow(10, 5):

return

if int(last) != 0:

dfs(int(str(n) + str(int(last)-1)), dp)

dfs(int(str(n) + last), dp)

if int(last) != 9:

dfs(int(str(n) + str(int(last)+1)), dp)

for i in range(1, 10):

dfs(i, dp)

cnt = 0

for i, v in enumerate(dp):

if v:

cnt += 1

if cnt == k:

print(i)

exit()